强化学习 · 第四章 · 专题动画

从一组方程
到一套算法

上一章把长期问题压缩成贝尔曼方程;这一章回答最后一跳:这组方程到底怎么解。同样是解方程,手里的信息不同,走的路也不同。

① 策略迭代 ② 值迭代 ③ DP 与 LP ④ 采样强化学习 ⑤ GPI
一句话方程不变;变的只是期望怎么算、最优怎么找、状态装不装得下。
这一章的解方程控制台
V = R + γPV · V* = maxa Q*
先看手里有什么信息
DP模型已知、状态可枚举:全枚举期望,反复做备份
LP模型已知:把 max 展开成约束,换一个优化视角
采样模型未知:用真实走一步,代替期望求和
04.1 · 策略迭代

评估一步,改进一步,直到不再变化

① 策略迭代› ② 值迭代› ③ DP·LP› ④ 采样› ⑤ GPI
每一圈 = 一次“算清” + 一次“贪心” 当前策略 π 任意初始化 策略评估 解出 Vπ 策略改进 π′ ← 对 Q 贪心 π′ 变了吗? 没变 → 停;变了 → 回环 每圈都不会变差
1
策略评估:固定 π,把价值算清
直接解线性方程,或反复套用期望方程,逼近到满意精度。
2
策略改进:对 Q 取贪心
每个状态都改选 Qπ(s,a) 最大的动作。
3
Q 的骨架仍是“奖励 + 折扣未来”
Qπ(s,a) = R + γΣP·Vπ(s′):仍是上一章那条备份公式。
4
终止:π′ = π
新策略对自身已贪心,就满足贝尔曼最优方程。
闭环评估负责“算清现在”,改进负责“往上走一步”;两者交替,直到没有更好的动作可选。
04.1b · 两状态小世界演示

亲手跑一遍:评估、改进,再评估

① 策略迭代› ② 值迭代› ③ DP·LP› ④ 采样› ⑤ GPI
小世界 · 两个状态,每个状态两个动作 工作 +1 · 回家 +1 · 上班 / 躺平 0 折扣 γ = 0.9 s₁ 家 两个动作可选 s₂ 公司 发工资的地方 a₂ 躺平 · r = 0 a₁ 上班 · r = 0 a₁ 工作 · r = +1 a₂ 回家 · r = +1 Vπ₀ = 0 Vπ₁ = 9 Vπ₀ = 1.0 Vπ₁ = 10 = 策略当前选中的动作
屏幕上这些数字分别代表什么
V(s)这个状态以后一直按当前策略走下去,折扣奖励加起来的总和 —— 本轮 0 / 1.0,再评估 9 / 10
Q(s,a)即时奖励 + γ × 下一步状态的 V —— 本例依次算出 0.9、1.9、8.1、9.1
r 与 γr:走一步当场拿到的奖励(+1 或 0);γ = 0.9:下一步只算九折
当前策略π₀ = (家: 躺平,公司: 回家) · 随机初始化
贪心改进π₁ = (家: 上班,公司: 工作)
停机π₂ = π₁ · 策略不再变化
策略评估 · 固定 π₀,反复代入到不再变化
V(家) = 0 + 0.9·V(家) → 0  V(公司) = 1 + 0.9·V(家) → 1.0
读数:0 / 1 是走一步当场拿到的奖励,0.9 是 γ;解出的 0 / 1.0 = 按 π₀ 走时家 / 公司各值多少
策略改进 · 用刚解出的 Vπ₀ 比一步价码 Q
Q(家,上班) = 0 + 0.9 × 1.0 = 0.9 > 0(躺平)
Q(公司,工作) = 1 + 0.9 × 1.0 = 1.9 > 1.0(回家)
读数:0 / 1 是即时奖励,1.0 是公司的 V;0.9 / 1.9 = 先做这个动作一次,连同之后的价值
策略评估 · 固定 π₁,公司陷入工作自循环
V(公司) = 1 + 0.9·V(公司) → 10  V(家) = 0.9 × 10 → 9
读数:10 = 每轮 1 + 0.9×上一轮的极限(下方迭代轨迹的 ∞ 列);9 = 家的即时奖励 0 + 0.9 × 10
策略改进 · 用 Vπ₁ 再比一次 Q:两处都不换
家:上班 0 + 0.9 × 10 = 9 > 躺平 0 + 0.9 × 9 = 8.1
公司:工作 1 + 0.9 × 10 = 10 > 回家 1 + 0.9 × 9 = 9.1
读数:8.1 / 9.1 = 改选另一个动作后、再乘一步折扣的价码,都比现在的选择低
停机 · 改进不再改动任何一个状态
π₂ = π₁ = (上班, 工作) → π*,V* = (9, 10)
读数:9 / 10 就是最优价值 V*(家) / V*(公司),与上一轮评估完全一致
轮策略 π评估出的 V贪心之后
0 π₀ = (躺平, 回家) Vπ₀ = (0, 1.0) π₁ = (上班, 工作)变了
1 π₁ = (上班, 工作) Vπ₁ = (9, 10) π₂ = π₁不变
停 π′ = π → 输出 π* = (上班, 工作),V* = (9, 10)
括号内依次是 V(家)、V(公司);「贪心之后」这一列,就是下一行要用的新策略。
评估 π₀ 的迭代轨迹 · 每轮把等号右边的 V 换成上一轮的数值
k01234⋯∞
V(家)000已收敛,不再变化0
V(公司)01.001.00已收敛,不再变化1.0
评估 π₁ 的迭代轨迹 · 每轮 1 + 0.9×上一轮,一步步爬向 10
k01234⋯∞
V(家)000.901.712.44⋯9
V(公司)01.001.902.713.44⋯10
为什么必停每一轮都严格变好,而两状态两动作一共只有 4 种策略——有限轮之后,必然 π′ = π。
04.2 · 策略改进定理

为什么贪心一步,不会把策略改坏

① 策略迭代› ② 值迭代› ③ DP·LP› ④ 采样› ⑤ GPI
Qπ(s,π′(s)) = maxa Qπ(s,a) ≥ Vπ(s)
数字哪里来 · 上一章三动作算例(状态 s,π = 0.5 / 0.3 / 0.2)
a₁π=0.5Q=+1.20
a₂π=0.3Q=+0.50
a₃π=0.2Q=−0.30
旧策略加权 Vπ
0.69
= 0.5×1.20 + 0.3×0.50 + 0.2×(−0.30)
贪心动作 Qπ(s,π′)
1.20
= max{1.20, 0.50, −0.30} = Q(s,a₁)
+0.51这一步立刻拿到的优势;未来再按新策略展开,价值只会继续抬升。
第一步:看一步 Q
把新策略代入旧价值,先得到一个不低于 Vπ 的起点:Qπ(s,π′(s)) ≥ Vπ(s)。
解法:maxa Qπ(s,a) = Q(s,a₁) = 1.20 ≥ Vπ(s) = 0.69
第二步:反复代入
每一步都不降,未来每一次备份也都不降,因此整条价值轨迹满足 Vπ′ ≥ Vπ。
解法:把 Vπ′ ≥ 1.20 代回 Vπ′=Rπ′+γPπ′Vπ′,下界只升不降 ⇒ Vπ′ ≥ 1.20 ≥ 0.69
单调性策略可以不变,但绝不会越改越差;有限个策略 + 严格改进 = 策略迭代必然终止。
04.3 · 何时停,贵在哪

终止条件很干脆,代价却藏在内层

① 策略迭代› ② 值迭代› ③ DP·LP› ④ 采样› ⑤ GPI
停机:策略不再变化
π′ = π
再改也没有更好的动作可选,当前策略满足贝尔曼最优方程。
|A||S|
确定性策略总数
3² = 9
两状态三动作的玩具例
成本画像:贵在“评估做满”
解方程O(n³)
一次备份O(n²)
状态规模n 大 → 痛
轮数少,不代表总成本低:每一轮都要先把评估做透。
问能不能少评估一点?
不等旧策略完全收敛,提前进入改进。
→
答只做一次备份:值迭代
评估与改进合并成一步,用更便宜的轮次换更多轮数。
取舍策略迭代是“想清楚再走”,值迭代是“边走边想”。下一幕把这条更便宜的路线拆开。
04.4 · 值迭代

不等评估做满,每轮只做一次最优备份

① 策略迭代› ② 值迭代› ③ DP·LP› ④ 采样› ⑤ GPI
值迭代Vk+1(s) = maxa [ R(s,a) + γ Σs′P(s′|s,a) Vk(s′) ] 右端就是贝尔曼最优算子 T*:从任意 V0 出发,反复应用它。
s₁ s₂ s₃ s₄ 迈入出口 r = 1 s₅ 出口 0 0 → .729 0 → .810 0 → .900 0 → 1.000 0 γ = 0.9;每轮更新全体状态,奖励像波一样向左侧扩散
ks₁s₂s₃s₄s₅
000000
10001.0000
2000.9001.0000
300.8100.9001.0000
40.7290.8100.9001.0000
收敛后对 V* 做一次贪心,就能导出 π*。
第 1 轮备份 · 每个状态做一次「奖励 + γ × 后继价值」
V₁(s₄) = 1 + 0.9 × V₀(s₅) = 1 + 0.9×0 = 1.000  V₁(s₁..s₃) = 0 + 0.9 × 0 = 0
读数:1 是迈进出口的奖励,0.9 是 γ;V₀ 全是 0,所以第一轮只有 s₄ 亮起来(走廊里每格只有「前进」一条路,max 不用比)
第 2 轮备份 · 奖励往左传一格,旧格子照旧更新
V₂(s₃) = 0 + 0.9 × V₁(s₄) = 0.9 × 1.000 = 0.900  V₂(s₄) = 1 + 0.9 × V₁(s₅) = 1.000
读数:走一步自己的奖励是 0,所以每往左挪一格就乘一次 0.9;s₄ 那一格已经到顶,保持 1
第 3、4 轮备份 · 同一个式子继续往左推,直到 s₁
V₃(s₂) = 0 + 0.9 × V₂(s₃) = 0.9 × 0.900 = 0.810
V₄(s₁) = 0 + 0.9 × V₃(s₂) = 0.9 × 0.810 = 0.729
读数:整条走廊收敛到 (0.729, 0.810, 0.900, 1.000, 0),就是 V*;每轮只做一次这样的备份,就是值迭代
为什么一定收敛上一章已经证明 T* 是 γ-压缩:每扫一遍,离 V* 的距离至多剩原来的 γ 倍。
04.5 · 两种迭代的谱系

不是对立,只是评估做了几次

① 策略迭代› ② 值迭代› ③ DP·LP› ④ 采样› ⑤ GPI
同一个旋钮:每轮评估做几次?
1 次
值迭代
k 次
截断策略迭代
做满
策略迭代
示例:还是「公司」这一格(工作 +1,γ = 0.9)
评估一次 = V ← 1 + 0.9 × V
四个数是同一式子的第 k 次结果:算得越多,越贴近 V* = 10
值迭代
1.00
评估 1 次
截断策略迭代
2.71
评估 3 次
截断策略迭代
6.51
评估 10 次
策略迭代
10.00
做到收敛
每轮成本与轮数
策略迭代轮数少
策略迭代每轮贵
值迭代轮数多
值迭代每轮便宜
把初始误差压到 1/1000 的轮数
γ = 0.966
γ = 0.99688
轮数 k ≈ ln1000 / ln(1/γ):γ 越接近 1 压缩越弱,66 → 688,十倍还多。
还可以更灵活:只扫一部分状态(异步 DP),或优先更新变化大的状态(优先扫描)。
选择状态不多、想少走几轮 → 策略迭代;状态很多、单轮要便宜 → 值迭代。
04.6 · DP 的门槛与线性规划

模型已知之后,还有一道规模门槛

① 策略迭代› ② 值迭代› ③ DP·LP› ④ 采样› ⑤ GPI
线性规划minV ΣsV(s) s.t. V(s) ≥ R(s,a) + γ Σs′P(s′|s,a)V(s′) ∀s,a 把 max 展开成“每个动作都成立”的不等式;最优解处约束最紧。
1
模型已知
P 与 R 必须能查询,否则期望和 max 都算不出来。
2
状态可枚举
每轮扫描所有状态;状态越大,单轮成本越高。
!
维数灾难
状态数随变量个数指数增长;每轮都要扫全表,结构上就扛不住。
把整张 V 表当成一个点:怎么读这张图
①横轴 V(家)、纵轴 V(公司):随便猜一组值,就是图上一个点(如左下的「猜的 3, 4」)。
②每条备份不等式画成一条线:要「不违反」,点就只能待在线的一侧。
③目标是把总和压小:只能往左下推,推到不能再推 = 两线交点。
算一下:公司 ≥ 1 + 0.9×公司 ⟹ 公司 ≥ 10;家 ≥ 0.9×公司 ⟹ 家 ≥ 9;最小和 = 19。
LP 的理论意义大;工程上,值迭代通常更直接。
V(家):家的价值 → ↑ V(公司):公司的价值 猜的 (3, 4) 公司 ≥ 1 + 0.9 × 公司(工作)⟹ 公司 ≥ 10 家 ≥ 0.9 × 公司(从家上班) 可行域 这些点都违反某条备份 9 10 V(家)+V(公司) = 19 顶点 V*
阴影 = 所有「不违反备份」的 (V(家), V(公司)),只剩右上角一小块;红虚线是目标和 19 的等值线,压到底就停在顶点。另两条备份在这里是松的。
同一件事DP 在状态空间里扫表,LP 在可行域里找顶点;都在解同一组最优方程。
04.7 · 从期望到样本

模型不知道,就用真实走一步代替求和

① 策略迭代› ② 值迭代› ③ DP·LP› ④ 采样› ⑤ GPI
有模型:对全部下一状态求和
Σs′ P(s′|s,a) V(s′)
当前 (s,a)
↘s′₁概率0.7价值V₁
↗s′₂概率0.3价值V₂
= 0.7 × V₁ + 0.3 × V₂
两条支路都要算,按概率加权
无模型:走一步,拿一个样本
样本平均 ≈ E[V(s′)]
真实一步
→实际落到s′ = s′₂
→带回价值V(s′₂) = V₂
= V₂
这次 0.7 那条没抽到,只拿到 0.3 那条的样本;多走几次取平均,才逼近 0.7×V₁ + 0.3×V₂
屏幕上这些数字分别是什么
0.7 / 0.3 转移概率 P:同一个动作,有 70% 的机会落到 s′₁、30% 的机会落到 s′₂(两条加起来 = 1,所以才需要“求和”)。
V₁ / V₂ 真的落到 s′₁ / s′₂ 之后,那个状态本身值多少,也就是备份里的 V(s′)。
估计值 ← 估计值 + α [ 目标 − 估计值 ]
α 是学习率(取 0 到 1):这一步的新信息占多少权重;γ 是折扣,和前面一样 0.9。
方括号里是误差信号;目标怎么取,决定了算法叫什么名字。
蒙特卡洛:目标 = 整条轨迹回报 时序差分:目标 = 一步奖励 + γV(s′) 自举:有偏,但方差更小
分界线不在“用不用神经网络”,而在期望怎么算:求和还是采样。
04.8 · 同策略与异策略

下一个动作怎么选,分出了两个家族

① 策略迭代› ② 值迭代› ③ DP·LP› ④ 采样› ⑤ GPI
SARSA · 同策略
r + γ Q(s′, a′)
a′ 是行为策略真正选出的下一个动作
行为策略 = 目标策略
Q-LEARNING · 异策略
r + γ maxa Q(s′, a)
不管行为策略,直接假设下一步选最优
行为策略 ≠ 目标策略
这两个算法后面会详细讲解;这里先用同一个数字例子,让它们各走一步,看差别落在哪一个数上。
算例目标误差项更新后的 Q
已知Q = 0.50,r = 0.20,γ = 0.9步长 α = 0.10—
SARSA0.20 + 0.9 × 0.60 = 0.740.74 − 0.50 = 0.240.50 + 0.10×0.24 = 0.524
Q-Learning0.20 + 0.9 × 0.80 = 0.920.92 − 0.50 = 0.420.50 + 0.10×0.42 = 0.542
把表格拆成四步算:0.20 是这一步真拿到的奖励,0.9 是折扣 γ(未来打 9 折),0.10 是学习率 α(只信十分之一),0.50 是现在的估计
绿色 = SARSA(下一步用真会选的那个动作 Q = 0.60) | 金色 = Q-Learning(下一步用最好的那个动作 Q = 0.80)
① 目标:这一步实际值多少
0.20 + 0.9 × 0.60 = 0.74
0.20 + 0.9 × 0.80 = 0.92
② 误差:比 0.50 高多少
0.74 − 0.50 = 0.24
0.92 − 0.50 = 0.42
③ 改动:只挪十分之一
0.10 × 0.24 = 0.024
0.10 × 0.42 = 0.042
④ 新估计:旧值加改动
0.50 + 0.024 = 0.524
0.50 + 0.042 = 0.542
为什么不直接把 0.50 改成 0.74?因为 α = 0.10 只让它信这一步 10%。两个算法的差别全在第一步:未来按 0.60 还是 0.80 折,目标就差 0.18,最后的值只差 0.018。
离散动作:SARSA / Q-Learning 是常见起点 连续动作:max 不好取,转向策略梯度 Actor-Critic:策略 + Critic,再降方差
一句话SARSA 把“我实际会怎么走”算进去;Q-Learning 把“理论上最好怎么走”当成目标。
04.9 · 广义策略迭代与选择

评估与改进互相拉扯,最后停在同一点

① 策略迭代› ② 值迭代› ③ DP·LP› ④ 采样› ⑤ GPI
评估 让 V 逼近 Vπ 改进 让 π 对 V 贪心 固定 V,改 π 固定 π,改 V 不动点 V*, π* 两条绳互相拉,最后只能停在“彼此都满意”的点 几乎所有价值型 RL 算法,都是这张图的变体
1
模型能不能拿到?
能 → DP / LP;不能 → 采样方法。
2
动作离散还是连续?
离散 → 可以 max;连续 → 策略梯度。
3
数据能不能反复用?
能反复用 → 异策略;只能用新采的 → 同策略。
结果三个问题答完,大部分算法选项已经被排除。
一条轨迹 → 一组方程 → 三条解法 → 一套算法地图
片尾 · 出品说明
朝露记
强化学习 · 第四章 · 专题动画
朝露记出品
内容梳理 讲解配音 动画编排
第四章 · 完 下一章 · 从一套算法到一页纸
解
00:00 / 19:58
空格 播放/暂停 ← → 切幕 R 重播 1–0 跳转